#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <malloc.h>
#include <unistd.h>
#include <assert.h>

typedef int DataType;
typedef struct TreeNode{
	DataType data;
	struct TreeNode* pLeft;
	struct TreeNode* pRight;
}	TreeNode;

TreeNode* CreateRoot(DataType data)
{
	TreeNode* pNode = (TreeNode *)malloc(sizeof(TreeNode));
	assert(pNode);
	pNode->data = data;
	pNode->pLeft = NULL;
	pNode->pRight = NULL;

	return pNode;
}

//用后序的最后一个创建根结点
////然后在中序中找后序的最后一个结点，同时计算长度
////找到之后左边的就是左子树，右边的就是右子树
////如果长度等于0就表示没有左子树，只用创建右子树
////如果长度等于size就表示没有右子树，只创建左子树
TreeNode* Recon(int* in_start, int* in_end, int* post_start, int* post_end)
{
	TreeNode* pRoot = CreateRoot(*post_end);
	if (in_start == in_end) {
		if (post_start == post_end && *in_start == *post_end) {
			return pRoot;
		}
		return NULL;
	}

	int* FindRoot = in_start;
	while (*FindRoot != *post_end) {
		FindRoot = FindRoot + 1;
		if (FindRoot > in_end){
			return NULL;
		}
	}
	int len = FindRoot - in_start;

	if (len <= 0) {
		pRoot->pRight = Recon(in_start + 1, in_end, post_start, post_end - 1);
	}
	else if (len == (in_end - in_start) + 1) {
		pRoot->pLeft = Recon(in_start, in_end - 1, post_start, post_end - 1);
	}
	else {
		pRoot->pLeft = Recon(in_start, in_start + len - 1, post_start, post_start + len - 1);
		pRoot->pRight = Recon(in_start + len + 1, in_end, post_start + len, post_end - 1);
	}

	return pRoot;
}

TreeNode* Reconstruct(DataType* PostOrder, DataType* InOrder, int size)
{
	if (PostOrder == NULL || InOrder == NULL) {
		return NULL;
	}

	return Recon(InOrder, InOrder + size - 1, PostOrder, PostOrder + size - 1);
}

void PrePri(TreeNode* pRoot)
{
	if (pRoot == NULL) {
		return;
	}

	printf("%d  ", pRoot->data);
	PrePri(pRoot->pLeft);
	PrePri(pRoot->pRight);
}

int Judge(DataType* start, DataType* end)
{
	DataType temp = *end;
	DataType* right = end;
	DataType* left = start;
	while (left < right){
		if (*left > temp){
			break;
		}
		left++;
	}
	if (left == right){		//只有左子树，且满足二叉搜索树
		return 1;
	}

	DataType* issmall = left;
	for (; issmall < right; issmall++){
		if (*issmall < temp){
			return -1;
		}
	}

	return Judge(start, left - 1) && Judge(left, right - 1);
}

int IsBackOrder(DataType* arr, int size)
{
	if (arr == NULL || size == 0){
		return -1;
	}
	return Judge(arr, arr + size - 1);
}

int main()
{
	DataType InOrder[] = { 9, 5, 8, 3, 7, 2, 1, 4 };
	DataType PostOrder[] = { 9, 8, 5, 2, 4, 1, 7, 3 };

	int size = sizeof(InOrder) / sizeof(DataType);
	TreeNode* pRoot = Reconstruct(PostOrder, InOrder, size);
	PrePri(pRoot);
	printf("\n");

	system("pause");
	return 0;
}

